Maratones competidas/Maratón Nacional 2011/workspace/c/c.cpp

   1 // Equipo Poncho, Carriel y Ruana
   2 using namespace std;
   3 #include <algorithm>
   4 #include <iostream>
   5 #include <iterator>
   6 #include <sstream>
   7 #include <fstream>
   8 #include <cassert>
   9 #include <climits>
  10 #include <cstdlib>
  11 #include <cstring>
  12 #include <string>
  13 #include <cstdio>
  14 #include <vector>
  15 #include <cmath>
  16 #include <queue>
  17 #include <stack>
  18 #include <list>
  19 #include <map>
  20 #include <set>
  21
  22 template <class T> string toStr(const T &x)
  23 { stringstream s; s << x; return s.str(); }
  24 template <class T> int toInt(const T &x)
  25 { stringstream s; s << x; int r; s >> r; return r; }
  26
  27 #define For(i, a, b) for (int i=(a); i<(b); ++i)
  28 #define foreach(x, v) for (typeof (v).begin() x = (v).begin(); x != (v).end(); ++x)
  29 #define D(x) cout << #x " = " << (x) << endl;
  30
  31 const double EPS = 1e-9;
  32
  33 int cmp(double x, double y = 0, double tol = EPS) {
  34     return (x <= y + tol) ? (x + tol < y) ? -1 : 0 : 1;
  35 }
  36
  37 #define INPUT_FILE "compression"
  38
  39 const int MAXBASES = 105, oo = 1 << 28;
  40 set<int> bases[MAXBASES];
  41
  42 int B, D;
  43 int bit[20]; // bit[i] = index of term i in the document
  44
  45 int memo[MAXBASES][1 << 16];
  46
  47
  48 bool compatible(const set<int> &base) {
  49     foreach(x, base) {
  50         int term = *x;
  51         if (bit[term] == -1) return false; // base tiene un elemento que el doc no tiene
  52     }
  53     return true;
  54 }
  55
  56 int maskOfBase(const set<int> &base) {
  57     int ans = 0;
  58     foreach(x, base){
  59         int term = *x;
  60         ans = ans | (1 << bit[term]);
  61     }
  62     return ans;
  63 }
  64
  65 int f(int b, int mask, const set<int> &doc) {
  66     int n = doc.size();
  67
  68     if (b == B) { // Vi todas las bases
  69         return (mask == ((1 << n) - 1) ? 0 : oo);
  70     }
  71     //assert(b < B);
  72     //printf("b = %d\n", b);
  73     if (memo[b][mask] != -1) return memo[b][mask];
  74
  75     if (!compatible(bases[b])) {
  76         return memo[b][mask] = f(b + 1, mask, doc);
  77     }
  78
  79     //assert(compatible(bases[b]));
  80
  81     // cojo esta base
  82     int ans = f(b + 1, mask | maskOfBase(bases[b]), doc) + 1;
  83
  84
  85     // no la cojo
  86     ans = min(ans, f(b + 1, mask, doc));
  87     return memo[b][mask] = ans;
  88 }
  89
  90 void solve(const set<int> &doc) {
  91     //puts("doc: "); foreach(x, doc) printf("%d ", *x); puts("");
  92     memset(bit, -1, sizeof bit);
  93
  94     int k = 0;
  95     foreach(x, doc) {
  96         int term = *x;
  97         bit[term] = k++;
  98     }
  99
 100     //For(i, 0, B) if (compatible(bases[i])) printf("Base i=%d: %d\n", i, maskOfBase(bases[i]));
 101
 102   //  for (int i = 0; i < 16; ++i) {
 103 //        printf("bit[%d] = %d\n", i, bit[i]);
 104 //    }
 105
 106     int ans = f(0, 0, doc);
 107     if (ans >= oo) ans = 0;
 108     printf("%d", ans);
 109 }
 110
 111 int main(){
 112     freopen(INPUT_FILE ".in", "r", stdin);
 113     while (cin >> B >> D) {
 114         if (B == 0 and D == 0) break;
 115         for (int i = 0; i < B; ++i) {
 116             bases[i].clear();
 117             int k; cin >> k;
 118             while (k--) {
 119                 int x; cin >> x; x--;
 120                 bases[i].insert(x);
 121             }
 122         }
 123
 124         for (int j = 0; j < D; ++j) {
 125             set<int> doc;
 126             int k; cin >> k;
 127             while (k--) {
 128                 int x; cin >> x; x--;
 129                 doc.insert(x);
 130             }
 131             memset(memo, -1, sizeof memo);
 132             solve(doc);
 133             if (j + 1 < D) printf(" ");
 134         }
 135         puts("");
 136
 137     }
 138     return 0;
 139
 140 }